`:top

`!Truncated binary encoding`! is an `F33f`_`[entropy encoding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Entropy_encoding]`_`f typically used for uniform `F33f`_`[probability distributions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Probability_distribution]`_`f with a finite alphabet. It is parameterized by an alphabet with total size of number `*n`*. It is a slightly more general form of `F33f`_`[binary encoding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_numeral_system]`_`f when `*n`* is not a `F33f`_`[power of two`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Power_of_two]`_`f.

If `*n`* is a power of two, then the coded value for 0 ≤ `*x`* < `*n`* is the simple binary code for `*x`* of length log2(`*n`*). Otherwise let `*k`* = floor(log2(`*n`*)), such that 2`*k`* < `*n`* < 2`*k`*+1and let `*u`* = 2`*k`*+1 − `*n`*.

Truncated binary encoding assigns the first `*u`* symbols codewords of length `*k`* and then assigns the remaining `*n`* − `*u`* symbols the last `*n`* − `*u`* codewords of length `*k`* + 1. Because all the codewords of length `*k`* + 1 consist of an unassigned codeword of length `*k`* with a "0" or "1" appended, the resulting code is a `F33f`_`[prefix code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Prefix_code]`_`f.

>>Contents

• `F0af`_`[History`#history]`_`f

• `F0af`_`[Example with n = 5`#example-with-n-5]`_`f

• `F0af`_`[Example with n = 10`#example-with-n-10]`_`f

• `F0af`_`[Example with n = 7`#example-with-n-7]`_`f

• `F0af`_`[Simple algorithm`#simple-algorithm]`_`f

• `F0af`_`[On efficiency`#on-efficiency]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>History

Used since at least 1984, `!phase-in codes`!, also known as `!economy codes`!,`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] are also known as truncated binary encoding.

>>Example with n = 5

For example, for the alphabet {0, 1, 2, 3, 4}, `*n`* = 5 and 22 ≤ `*n`* < 23, hence `*k`* = 2 and `*u`* = 23 − 5 = 3. Truncated binary encoding assigns the first `*u`* symbols the codewords 00, 01, and 10, all of length 2, then assigns the last `*n`* − `*u`* symbols the codewords 110 and 111, the last two codewords of length 3.

For example, if `*n`* is 5, plain binary encoding and truncated binary encoding allocates the following `F33f`_`[codewords`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Code_word_(communication)]`_`f. Digits shown struck are not transmitted in truncated binary.

`t

| Truncated binary | Encoding | Encoding | Encoding | Standard binary |

|---|---|---|---|---|

| 0 | 0 | 0 | 0 | 0 |

| 1 | 0 | 0 | 1 | 1 |

| 2 | 0 | 1 | 0 | 2 |

| UNUSED | 0 | 1 | 1 | 3 |

| UNUSED | 1 | 0 | 0 | 4 |

| UNUSED | 1 | 0 | 1 | 5/UNUSED |

| 3 | 1 | 1 | 0 | 6/UNUSED |

| 4 | 1 | 1 | 1 | 7/UNUSED |

`t

It takes 3 bits to encode `*n`* using straightforward binary encoding, hence 23 − `*n`* = 8 − 5 = 3 are unused.

In numerical terms, to send a value `*x`*, where 0 ≤ `*x`* < `*n`*, and where there are 2`*k`* ≤ `*n`* < 2`*k`*+1 symbols, there are `*u`* = 2`*k`*+1 − `*n`* unused entries when the alphabet size is rounded up to the nearest power of two. The process to encode the number `*x`* in truncated binary is: if `*x`* is less than `*u`*, encode it in `*k`* binary bits; if `*x`* is greater than or equal to `*u`*, encode the value `*x`* + `*u`* in `*k`* + 1 binary bits.

>>Example with n = 10

Another example, encoding an alphabet of size 10 (between 0 and 9) requires 4 bits, but there are 24 − 10 = 6 unused codes, so input values less than 6 have the first bit discarded, while input values greater than or equal to 6 are offset by 6 to the end of the binary space. (Unused patterns are not shown in this table.)

`t

| Input value | Offset | Offset value | Standard binary | Truncated binary |

|---|---|---|---|---|

| 0 | 0 | 0 | 0 000 | 000 |

| 1 | 0 | 1 | 0 001 | 001 |

| 2 | 0 | 2 | 0 010 | 010 |

| 3 | 0 | 3 | 0 011 | 011 |

| 4 | 0 | 4 | 0 100 | 100 |

| 5 | 0 | 5 | 0 101 | 101 |

| | | | | |

| 6 | 6 | 12 | 0110 | 1100 |

| 7 | 6 | 13 | 0111 | 1101 |

| 8 | 6 | 14 | 1000 | 1110 |

| 9 | 6 | 15 | 1001 | 1111 |

`t

To decode, read the first `*k`* bits. If they encode a value less than `*u`*, decoding is complete. Otherwise, read an additional bit and subtract `*u`* from the result.

>>Example with n = 7

Here is a more extreme case: with `*n`* = 7 the next power of 2 is 8, so `*k`* = 2 and `*u`* = 23 − 7 = 1:

`t

| Input value | Offset | Offset value | Standard binary | Truncated binary |

|---|---|---|---|---|

| 0 | 0 | 0 | 0 00 | 00 |

| | | | | |

| 1 | 1 | 2 | 001 | 010 |

| 2 | 1 | 3 | 010 | 011 |

| 3 | 1 | 4 | 011 | 100 |

| 4 | 1 | 5 | 100 | 101 |

| 5 | 1 | 6 | 101 | 110 |

| 6 | 1 | 7 | 110 | 111 |

`t

This last example demonstrates that a leading zero bit does not always indicate a short code; if `*u`* < 2`*k`*, some long codes will begin with a zero bit.

>>Simple algorithm

Generate the truncated binary encoding for a value `*x`*, 0 ≤ `*x`* < `*n`*, where `*n`* > 0 is the size of the alphabet containing `*x`*. `*n`* need not be a power of two.

`B100`F9d9string TruncatedBinary (int x, int n)`f`b

`B100`F9d9{`f`b

`B100`F9d9 // Set k = floor(log2(n)), i.e., k such that 2^k <= n < 2^(k+1).`f`b

`B100`F9d9 int k = 0, t = n;`f`b

`B100`F9d9 while (t > 1) { k++; t >>= 1; }`f`b

`B100`F9d9`f`b

`B100`F9d9 // Set u to the number of unused codewords = 2^(k+1) - n.`f`b

`B100`F9d9 int u = (1 << k + 1) - n;`f`b

`B100`F9d9`f`b

`B100`F9d9 if (x < u)`f`b

`B100`F9d9 return Binary(x, k);`f`b

`B100`F9d9 else`f`b

`B100`F9d9 return Binary(x + u, k + 1));`f`b

`B100`F9d9}`f`b

The routine `B100`F9d9Binary`f`b is expository; usually just the rightmost `B100`F9d9len`f`b bits of the variable `*x`* are desired. Here we simply output the binary code for `*x`* using `B100`F9d9len`f`b bits, padding with high-order 0s if necessary.

`B100`F9d9string Binary (int x, int len)`f`b

`B100`F9d9{`f`b

`B100`F9d9 string s = "";`f`b

`B100`F9d9 while (x != 0) {`f`b

`B100`F9d9 if (even(x))`f`b

`B100`F9d9 s = '0' + s;`f`b

`B100`F9d9 else s = '1' + s;`f`b

`B100`F9d9`f`b

`B100`F9d9 x >>= 1;`f`b

`B100`F9d9 }`f`b

`B100`F9d9 while (s.Length < len)`f`b

`B100`F9d9 s = '0' + s;`f`b

`B100`F9d9 return s;`f`b

`B100`F9d9}`f`b

>>On efficiency

If `*n`* is not a power of two, and `*k`*-bit symbols are observed with probability `*p`*, then (`*k`* + 1)-bit symbols are observed with probability 1 − `*p`*. We can calculate the expected number of bits per symbol b e {\\displaystyle b_{e}} as

b e = p k + ( 1 − − p ) ( k + 1 ) . {\\displaystyle b_{e}=pk+(1-p)(k+1).}

Raw encoding of the symbol has b u = k + 1 {\\displaystyle b_{u}=k+1} bits. Then relative space saving `*s`* (see `F33f`_`[Data compression ratio`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_compression_ratio]`_`f) of the encoding can be defined as

s = 1 − − b e b u = 1 − − p k + ( 1 − − p ) ( k + 1 ) k + 1 . {\\displaystyle s=1-{\\frac {b_{e}}{b_{u}}}=1-{\\frac {pk+(1-p)(k+1)}{k+1}}.}

When simplified, this expression leads to

s = p k + 1 = p b u . {\\displaystyle s={\\frac {p}{k+1}}={\\frac {p}{b_{u}}}.}

This indicates that relative efficiency of truncated binary encoding increases as probability `*p`* of `*k`*-bit symbols increases, and the raw-encoding symbol bit-length b u {\\displaystyle b_{u}} decreases.

>>See also

• `F33f`_`[Benford's law`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Benford's_law]`_`f

• `F33f`_`[Golomb coding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Golomb_coding]`_`f

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f Eastman, Willard L, `*et al.`* (Aug. 1984) Apparatus and Method for Compressing Data Signals and Restoring the Compressed Data Signals, US Patent 4,464,650.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f Acharya, Tinku et Já Já, Joseph F. (oct. 1996), An on-line variable-length binary encoding of text, Information Sciences, vol 94 no 1-4, p. 1-22.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f Job van der Zwan. "Phase-in Codes".

`c`F0af`_`[↑ Back to top`#top]`_`f`a